package xin.yangshuai.basic01.sort;

/**
 * Sort
 *
 * @author shuai
 * @date 2021/1/13
 */
public class Sort {

    public static void main(String[] args) {
        test(2, 4, 5, 8, 7, 9, 1);
        test(0, 9, 8, 7, 6, 5, 4, 3, 2, 1);
        test(8, 6, 7, 4, 5, 3, 4, 2, 1, 9);
        System.out.println("-----------------------");
        test1(2, 4, 5, 8, 7, 9, 1);
        test1(0, 9, 8, 7, 6, 5, 4, 3, 2, 1);
        test1(8, 6, 7, 4, 5, 3, 4, 2, 1, 9);

    }

    public static void test(int... array) {

        for (int i = 0; i < array.length; i++) {
            int temp0 = array[i];
            for (int j = 0; j < i; j++) {
                int temp1 = array[j];
                if (temp1 <= temp0) {
                    continue;
                } else {
                    for (int k = i; k > j; k--) {
                        array[k] = array[k - 1];
                    }
                    array[j] = temp0;
                    break;
                }
            }
        }

        for (int i : array) {
            System.out.print(i + "、");
        }
        System.out.println();
    }

    public static void test1(int... array) {
        test2(array, 0, array.length - 1);
        for (int i : array) {
            System.out.print(i + "、");
        }
        System.out.println();
    }


    public static void test2(int[] array, int start, int end) {

        if (start < end) {
            int index = test3(array, start, end);
            if (start < index - 1) {
                test2(array, start, index - 1);
            }
            if (index + 1 < end) {
                test2(array, index + 1, end);
            }
        }
    }

    public static int test3(int[] array, int start, int end) {
        if (start < end) {
            int startValue = array[start];

            while (start < end) {
                while (start < end && startValue <= array[end]) {
                    end--;
                }
                if (start < end) {
                    // 一旦较大索引的值小于选中的值，则把选中的值替换为较大索引的值
                    // 原始array[start]的值就是取出来的那个值，不怕丢
                    array[start] = array[end];
                } else {
                    array[start] = startValue;
                    return start;
                }
                //start先自增，自己不用跟自己比较
                start++;
                while (start < end && startValue >= array[start]) {
                    start++;
                }
                if (start < end) {
                    array[end] = array[start];
                } else {
                    array[start] = startValue;
                    return start;
                }
                end--;
            }
            array[start] = startValue;
            return start;
        } else {
            throw new RuntimeException("不该发生的异常");
        }
    }
}

